|
In combinatorial optimization, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree that represents the minimum ''s''-''t'' cuts for all ''s''-''t'' pairs in the graph. The Gomory–Hu tree can be constructed in | ''V'' | − 1 minimum cut computations. ==Definition== Let ''G'' = ((''V''G, ''E''G), ''c'') be an undirected graph with ''c''(''u'',''v'') being the capacity of the edge (''u'',''v'') respectively. : Denote the minimum capacity of an ''s''-''t'' cut by λst for each ''s'', ''t'' ∈ ''V''G. : Let ''T'' = (''V''T,''E''T) be a tree with ''V''T = ''V''G, denote the set of edges in an ''s''-''t'' path by ''P''st for each ''s'',''t'' ∈ ''V''T. Then ''T'' is said to be a Gomory–Hu tree of ''G'' if : λst = mine∈Pst ''c''(''S''e, ''T''e) for all ''s'', ''t'' ∈ ''V''G, where # ''S''e and ''T''e are the two connected components of ''T''∖ in the sense that (''S''e, ''T''e) form a ''s''-''t'' cut in ''G'', and # ''c''(''S''e, ''T''e) is the capacity of the cut in ''G''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Gomory–Hu tree」の詳細全文を読む スポンサード リンク
|